template <typename DT>
class List
{
    private:
        struct Node   //创建List双链表的节点Node。用struct默认公有没关系，因为Node是私有的
        {
            DT data;   //储存的数字
            Node *prev;  //指向上一个节点
            Node *next;  //指向下一个节点

            Node( const DT & d = DT{ }, Node *p = nullptr, Node *n = nullptr)  //和下一个重载
                : data{d}, prev{p}, next{n} {}

            Node(  DT && d, Node *p = nullptr, Node *n = nullptr)
                : data{std::move(d)}, prev{p}, next{n} {}
        };

    public:
        class const_iterator   //常数迭代器，不改变项本身
        {
            public:
                const_iterator(): current{nullptr}   //指向"当前"的指针
                {}

                const DT & operator*() const    //*
                {return retrieve();}
        
                const_iterator & operator++()  //重载：前缀后缀不一样：前缀为空参数表
                {
                    current = current->next;
                    return *this;
                }
                const_iterator & operator++(int)  //后缀为单参数int
                {
                    const_iterator old = *this
                    ++( *this);
                    return old;
                }

                bool operator==(const const_iterator & rhs) const   //==
                {return current == rhs.current;}
                bool operator!=(const const_iterator & rhs) const   //!=
                {return !(*this == rhs);}

            protected:   //默认私有的话iterator无权访问，这样继承者有权访问
                Node *current; //存储指向“当前”节点的指针

                DT & retrieve() const   //获得数据
                {return current->data;}

                const_iterator( Node* p): current{p}
                {}

                friend class List;  //赋予Lsit访问protected的权利 
        };


        class iterator : public const_iterator // 继承，意味着iterator就是个const_interator，可以添加新的数据和方法
        {  //非常数迭代器，会对项本身进行改动
            public:
                iterator()
                {}

                DT & operator*()  //给operator*提供一对访问/修改函数
                {return const_iterator::retrieve();}
                const DT & operator*() const
                {return const_iterator::operator*();} //直接使用const_interator，显式，否则会被新版隐藏

                iterator & operator++()  //提供新的operator++实现（返回类型改变）
                {
                    this->current = this->current->next;
                    return *this;
                }
                iterator operator++(int)   
                {
                    iterator old = *this;
                    ++(*this);
                    return old;
                }

            protected:
                iterator( Node *p ) : const_iterator{ p }{}
                friend class List<DT>;
        };
        //--------------------------------------------构造函数、五大函数和私有init例程
        List()  //零参数构造函数
            {init( );} //创建空List
        
        ~List()  //析构函数
        {
            clear();
            delete head;
            delete tail;
            //调用公有方法而不是低水平指针操作
        }

        List(const List & rhs)    //构造函数
        {
            init();
            for(auto & x: rhs)
                push_back(x);
        }

        List & operator=(const List & rhs)  //拷贝构造函数，用于operator=的实现
        {
            List copy = rhs;
            std::swap(*this, copy);
            return *this;
        }

        List(List && rhs)   //初始化rhs
            :theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail}
        {
            rhs.theSize = 0;
            rhs.head = nullptr;
            rhs.tail = nullptr;
        }

        List & operator= (List && rhs) //赋值
        {
            std::swap(theSize, rhs.theSize);
            std::swap(head, rhs.head);
            std::swap(tail, rhs.tail);

            return *this;
        }

        /*void init()
        {
            theSize = 0;
            head = new Node;
            tail = new Node;
            head->next = tail;
            tail->prev = head;
        }*/

        //---------------------------------------------------

        iterator begin()    //重载的起始和末尾符
        {return {head->next};}  //返回相应的迭代器
        const_iterator begin() const
        {return {head->next};}
        iterator end()
        {return {tail};}
        const_iterator end() const
        {return {tail};}  

        int size() const   //返回大小;
        {return theSize;}
        bool empty() const   //是否是空的;
        {return size() == 0;}

        void clear() //清空, 避免染指回收节点的工作，这都交由pop_front处理
        {
            while(!empty())
                pop_front();
        }      

        //---------------------------------------------通过获得并使用适当的迭代器
        DT & front()   //前端
            {return *begin();}
        const DT & front() const
            {return *begin();}

        DT & back()   //末端
            {return *--end();}
        const DT & back() const
            {return *--end();}

        void push_front(const DT & x)  //在List前端插入
            {insert(begin(),x);}  //注意insert是在一个位置前插入，push_back在终点标记前插入
        void push_front(DT && x)
            {insert(begin, std::move(x));}
        
        void push_back(const DT & x)  //在List末端插入
            {insert(end(),x);}
        void push_bacl(DT && x)
            {inert(end(), std::move(x));}
        
        void pop_front()  
            {erase(begin());}
            // 创建对应终端标记的临时迭代器，后撤该临时迭代器，并对其执行erase。下面pop_back同理，也避免了回收节点工作
        void pop_back()
            {erase(--end());}
        
        //---------------------------------------------在itr前插入x 
        iterator insert(iterator itr, const DT & x)
        {
            Node *p = itr.current;
            theSize++;
            return {p->prev = p->prev->next = new Node{x, p->prev ,p}};
        }
        iterator insert(iterator itr,  DT && x)
        {
            Node *p = itr.current;
            theSize++;
            return {p->prev = p->prev->next = new Node{std::move(x), p->prev ,p}};
        }

        //--------------------------------------------删除在itr处的项
        iterator erase(iterator itr)  //逐个删
        {
            Node *p = itr.current;
            iterator retVal{p->next};
            p->prev->next = p->next;
            p->next->prev = p->prev;
            delete p;
            theSize--;

            return retVal;
        }
        iterator erase(iterator from, iterator to)  // 批量删
        {
            for(iterator itr = from; itr != to;)    //注意此处不能直接itr++，因为已经过时了，这也是上面erase要返回一个interator的原因
                itr = erase(itr);
            
            return to;
        }

    private:
        int theSize;   //大小
        Node *head;    //头结点
        Node *tail;    //尾结点

        void init()    //零参数构造函数必须配置头尾结点;
        {
            theSize = 0;
            head = new Node;
            tail = new Node;
            head->next = tail;
            tail->prev = head;
        }
};